Generalized tree alignment
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
In computational phylogenetics, generalized tree alignment is the problem of producing a multiple sequence alignment and a phylogenetic tree on a set of sequences simultaneously, as opposed to separately.cite-ref-schwikowskivingron1997-1-0[1]
Formally, Generalized tree alignment is the following optimization problem.
Input: A set S {\displaystyle S} and an edit distance function d {\displaystyle d} between sequences,
Output: A tree T {\displaystyle T} leaf-labeled by S {\displaystyle S} and labeled with sequences at the internal nodes, such that Σ Σ e ∈ ∈ T d ( e ) {\displaystyle \Sigma _{e\in T}d(e)} is minimized, where d ( e ) {\displaystyle d(e)} is the edit distance between the endpoints of e {\displaystyle e} .cite-ref-aluru2005-2-0[2]
Note that this is in contrast to tree alignment, where the tree is provided as input.
References
cite-note-aluru2005-22. ↑ citerefsrinivas-aluru2005Srinivas Aluru (21 December 2005). Handbook of Computational Molecular Biology. CRC Press. pp. 19–26. ISBN 978-1-4200-3627-5.